package org.example.sword2offer.primary;
import java.util.*;
/**
 * @author: lynn
 * @Descript: 按之字形打印二叉树
 * 请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，
 * 第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推
 * https://blog.csdn.net/qq_28081081/article/details/80883641
 * @date: 2021/3/24 20:44
 * @version: 1.0
 */
public class Q58_ZprintTree {
    public static void main(String[] args) {
        TreeNode treeNode=new TreeNode(8);
        treeNode.left=new TreeNode(4);
        treeNode.right=new TreeNode(6);
        treeNode.left.left=new TreeNode(2);
        treeNode.left.right=new TreeNode(3);
        treeNode.right.left=new TreeNode(5);
        treeNode.right.right=new TreeNode(7);
        System.out.println(Print(treeNode));
    }
    public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>>  res =new ArrayList<>();

        if (pRoot==null){
            return res;
        }

        /**
         * 奇数行从左到右打印，偶数行从右到左打印。那么使用两个栈，一个栈存奇数行（先保存右子树再保存左子树），
         * 一个栈存偶数行（先保存左子树再保存右子树）。仔细分析下：第一行是奇数行，只有一个入奇数栈,然后出栈。
         * 出站的同时用偶数栈将该结点的左子树保存，再保存右子树，那么这样一来，下次取出偶数栈中的数据在树中看就是从左到右，
         * 取出的同时，用奇数栈将该结点的右子树保存，再保存左子树。这样一来，下次取出奇数栈中的数据在树中看就是从右到左
         *
         */
        Stack<TreeNode> stack1=new Stack<>(); //奇数行的栈
        Stack<TreeNode> stack2=new Stack<>(); //偶数行的栈
        LinkedList<TreeNode> linkedList=new LinkedList<>();
        stack1.push(pRoot);
        int lay=1;
        while(!stack1.isEmpty()||!stack2.isEmpty()){
            ArrayList<Integer> lineRes = new ArrayList<Integer>();
            if (lay%2==1){ //处理奇数栈,从左到右打印，由于用的是stack结构，先保存右子树再保存左子树
                while (!stack1.isEmpty()){
                    TreeNode node=stack1.pop();
                    if (node!=null) {
                        lineRes.add(node.val);
                        stack2.push(node.left);
                        stack2.push(node.right);
                    }
                }
            }else { //处理偶数栈，从右到左打印，由于用的是stack结构，先保存左子树再保存右子树
                while (!stack2.isEmpty()){
                    TreeNode node=stack2.pop();
                    if (node!=null) {
                        lineRes.add(node.val);
                        stack1.push(node.right);
                        stack1.push(node.left);
                    }
                }
            }
            if (lineRes.size()!=0){
                res.add(lineRes);
            }
            lay++;
        }
        return res;
    }

    private static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val=val;
        }
    }
}
